package algorithm.middle;

import java.util.HashSet;

/**
 * 请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 * <p>
 * 注意：
 * <p>
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-sudoku
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class IsValidSudoku36 {
    public boolean isValidSudoku(char[][] board) {
        int hang = board.length;
        int lie = board[0].length;
        //检查行
        for (int i = 0; i < hang; i++) {
            HashSet<Character> set = new HashSet<>();
            for (int j = 0; j < lie; j++) {
                if (board[i][j] != '.') {
                    if (!set.add(board[i][j])) return false;
                }
            }
        }
        //检查列
        for (int i = 0; i < lie; i++) {
            HashSet<Character> set = new HashSet<>();
            for (int j = 0; j < hang; j++) {
                if (board[j][i] != '.') {
                    if (!set.add(board[j][i])) return false;
                }
            }
        }
        //检查块块
        int m = 3;
        int n = 3;
        for (int h = 0; h < 9; h++) {
            if (n == 12) {
                m = m + 3;
                n = 3;
            }
            HashSet<Character> set = new HashSet<>();
            for (int i = m - 3; i < m; i++) {
                for (int j = n - 3; j < n; j++) {
                    if (board[i][j] != '.') {
                        if (!set.add(board[i][j])) return false;
                    }
                }
            }
            n = n + 3;
        }
        return true;
    }

    public static void main(String[] args) {
        boolean validSudoku = new IsValidSudoku36().isValidSudoku(new char[][]
                         {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}
                        , {'6', '.', '.', '1', '9', '5', '.', '.', '.'}
                        , {'.', '9', '8', '.', '.', '.', '.', '6', '.'}
                        , {'8', '.', '.', '.', '6', '.', '.', '.', '3'}
                        , {'4', '.', '.', '8', '.', '3', '.', '.', '1'}
                        , {'7', '.', '.', '.', '2', '.', '.', '.', '6'}
                        , {'.', '6', '.', '.', '.', '.', '2', '8', '.'}
                        , {'.', '.', '.', '4', '1', '9', '.', '.', '5'}
                        , {'.', '.', '.', '.', '8', '.', '.', '7', '9'}}
        );
        System.out.println(validSudoku);
    }
}
